public class Solution676 {

    static class Trie{
        boolean end;
        Trie[] tries=new Trie[26];

        public void insert(String t){
            Trie node=this;
            for (char c : t.toCharArray()) {
                if (node.tries[c-'a']==null){
                    node.tries[c-'a']=new Trie();
                }
                node=node.tries[c-'a'];
            }
            node.end=true;
        }

        public boolean query(String t,int remain,int pos,Trie trie){
            if (pos==t.length()){
                return remain==0 && trie.end;
            }
            for (int i=0;i<26;i++){
                if (trie.tries[i]!=null){
                    if (t.charAt(pos)-'a'==i){
                        if (query(t,remain,pos+1,trie.tries[i])){
                            return true;
                        }
                    }else if (remain==1){
                        if (query(t,0,pos+1,trie.tries[i])){
                            return true;
                        }
                    }
                }
            }
            return false;
        }
    }

    Trie trie=new Trie();

    public Solution676() {

    }

    public void buildDict(String[] dictionary) {
        for (String s : dictionary) {
            trie.insert(s);
        }
    }

    public boolean search(String searchWord) {
        return trie.query(searchWord,1,0,trie);
    }

    public static void main(String[] args) {
        Solution676 solution676=new Solution676();
        solution676.buildDict(new String[]{"hello", "leetcode"});
        System.out.println(solution676.search("hello"));
        System.out.println(solution676.search("hhllo"));
        System.out.println(solution676.search("hell"));
        System.out.println(solution676.search("leetcoded"));
    }
}
